package leetcode_1001_1100;

import java.util.*;

public class LeeCode_1042 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(gardenNoAdj(3, new int[][]{{1, 2}, {2, 3}, {3, 1}})));
    }
    private static class Node{
        public int flo = -1;
        public int val;
        public List<Node> ns;
        public Node(int val) {
            this.val = val;
            ns = new ArrayList<>();
        }
    }
    private static int[] gardenNoAdj(int n, int[][] paths) {
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i + 1);
        }
        for (int[] path : paths) {
            nodes[path[0] - 1].ns.add(nodes[path[1] - 1]);
            nodes[path[1] - 1].ns.add(nodes[path[0] - 1]);
        }
        for (Node node : nodes) {
            setFlo(node);
        }
        int[] ans = new int[n];
        for (int i = 0; i < nodes.length; i++) {
            ans[i] = nodes[i].flo;
        }
        return ans;
    }
    private static void setFlo(Node node){
        Set<Integer> set = new HashSet<>();
        for (Node n : node.ns) {
            set.add(n.flo);
        }
        for (int i = 1; i <= 4; i++) {
            if (!set.contains(i)){
                node.flo = i;
                return;
            }
        }
    }
}
